Computers represent a well developed body of art. Many computers include both a processor and associated memory. The memory is used to store software. In many cases, the software stored in memory includes an operating system and one or more applications. In normal operation, the applications are supported by both the processor as well as the operating system.
The C language is similar to many other computer languages in that those languages provide for instructions which implement a selection from among a group based on the test of a single value. As an example, FIG. 1 illustrates a Case statement. The Case statement is a powerful programming tool and is often used in programs designed to decode a stream of data. A program that parses text into tokens such as a compiler may use a Case statement. A program that simulates a computer architecture may use a Case statement to decode machine instructions and dispatch subroutines to carry out the instruction operations. FIG. 1 is an example of the use of several Case statements. Based on the value of the parameter x, the statements allow a selection as well as a default selection in the event that the parameter x does not match any of the predetermined selections.
While the Case statement and similar instructions in other languages are powerful tools, they exhibit poor performance (relative to other less powerful statements). Case statements do not translate well from a high level language to machine language.
An efficient translation of a Case statement involves converting the parameter, or target item x, into a token and then matching that token (derived from the parameter x) to a token/subroutine relation pair. A typical example is the problem presented when decoding Java (TM) instructions. There are 256 possible Java instructions. The Java instruction is converted into a parameter like the parameter x, hereinafter referred to as a token. Since there are 256 Java instructions, there are 256 subroutines in the Java interpreter, each with a task of processing the action of a Java instruction. The token/subroutine matching involves matching the Java instruction token x to the subroutine responsible for processing that instruction.
The token/subroutine pair is normally expressed in a table of addresses indexed by the token derived from the parameter x. Therefore, the operation of the Case statement in an abstract machine language would take on the form of the four statements shown in FIG. 2A. As shown in FIG. 2A, the first statement, the load statement, loads the register 1 with a Java instruction token (i.e. the parameter x). The second statement processes the token to make it into an index (in this case multiplying it by 4 to account for 4-byte wide addresses). The next statement uses the result produced in the multiply statement as an index into a table to extract the corresponding target subroutine address. In the third statement, this address is then loaded into register 2 so that the following statement, the branch, allows a jump to the target subroutine for processing the Java instruction.
The actual assembler operation specifics will vary from machine to machine but the basic operation does not change. For example, the PowerPC instruction set requires five instructions to perform this Case operation. The x86 instruction set requires three instructions. However, every modern processor architecture suffers from a pipeline stall during this particular translation. Thus, the present invention would improve performance of PowerPC (or RISC processors), X86 descendant processors, and the newly developing JAVA processors. The stall is due to the well known "computed goto" nature of the Case statement. Until the branch operation is implemented (in the fourth statement of FIG. 2A), the processor is unaware of the destination and therefore must stall until that address is available. The address does not become available until late in the operation sequence.
To provide a solution to the problem, the present invention is directed at providing an inexpensive and simple multi-way branch instruction. While the problem presented by interpreting or decoding Java instructions has been presented, the solution which will be described is applicable to similar, traditionally poor performing operations. Any computing operation that takes a token and must branch to a unique location based on the token will benefit. Aside from the Java example noted above, other similar operations include:
1. Parsing operations such as word processors and network switching.
2. Simulators such as Apple's highly used 68000 emulator with a PowerPC.